/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-11-14
 * Time: 16:37
 */
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.*;
import java.util.stream.Collectors;

/**
 * LRU页面置换算法实验实现
 * 功能：支持手动/文件输入页面序列，模拟LRU置换，统计命中率，输出详细过程
 */
public class LRUPageReplacement {

    // 存储单次访问结果的实体类
    static class AccessResult {
        int seqNum;       // 访问序号
        int page;         // 访问页面
        List<Integer> blocks; // 物理块状态
        String result;    // 访问结果（命中/未命中）

        public AccessResult(int seqNum, int page, List<Integer> blocks, String result) {
            this.seqNum = seqNum;
            this.page = page;
            this.blocks = blocks;
            this.result = result;
        }
    }

    // 存储统计结果的实体类
    static class Statistic {
        int totalAccess;  // 总访问次数
        int hitCount;     // 命中次数
        int missCount;    // 未命中次数
        double hitRate;   // 命中率（%）

        public Statistic(int totalAccess, int hitCount, int missCount, double hitRate) {
            this.totalAccess = totalAccess;
            this.hitCount = hitCount;
            this.missCount = missCount;
            this.hitRate = hitRate;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("===== LRU页面置换算法模拟实验 =====");

        // 1. 输入物理块数量（支持测试3和4）
        int blockNum = inputPhysicalBlocks(scanner);

        // 2. 输入页面访问序列（手动/文件读取）
        List<Integer> pageSequence = inputPageSequence(scanner);

        // 3. 执行LRU算法模拟
        Map<String, Object> simulationResult = simulateLRU(blockNum, pageSequence);
        List<AccessResult> accessResults = (List<AccessResult>) simulationResult.get("accessResults");
        Statistic statistic = (Statistic) simulationResult.get("statistic");

        // 4. 输出结果
        printAccessTable(accessResults);
        printStatistic(statistic);

        // 5. 可选：测试另一个物理块数量（如3之后测试4）
        System.out.print("\n是否测试另一个物理块数量？（Y/N）：");
        String choice = scanner.next().toUpperCase();
        if (choice.equals("Y")) {
            main(args); // 递归重新执行
        } else {
            System.out.println("访问结束！");
        }

        scanner.close();
    }

    /**
     * 输入物理块数量（验证范围1-10）
     */
    private static int inputPhysicalBlocks(Scanner scanner) {
        int blockNum = 0;
        while (true) {
            System.out.print("请输入物理块数量（1-10）：");
            try {
                blockNum = scanner.nextInt();
                if (blockNum >= 1 && blockNum <= 10) {
                    break;
                } else {
                    System.out.println("错误：物理块数量必须在1-10之间！");
                }
            } catch (InputMismatchException e) {
                System.out.println("错误：请输入整数！");
                scanner.next(); // 清除非法输入
            }
        }
        return blockNum;
    }

    /**
     * 输入页面访问序列（支持手动输入或文件读取）
     */
    private static List<Integer> inputPageSequence(Scanner scanner) {
        List<Integer> pageSequence = new ArrayList<>();
        while (true) {
            System.out.print("请选择页面序列输入方式（1.手动输入 2.文件读取）：");
            int choice = 0;
            try {
                choice = scanner.nextInt();
                scanner.nextLine(); // 清除换行符
                if (choice == 1) {
                    // 手动输入：格式如 7,0,1,2,0,3,...
                    System.out.print("请输入页面序列（逗号分隔非负整数）：");
                    String input = scanner.nextLine().trim();
                    pageSequence = parsePageSequence(input);
                    if (!pageSequence.isEmpty()) break;
                    else System.out.println("错误：页面序列不能为空！");
                } else if (choice == 2) {
                    // 文件读取：文件中一行存储页面序列（逗号分隔）
                    System.out.print("请输入文件路径：");
                    String filePath = scanner.nextLine().trim();
                    pageSequence = readPageSequenceFromFile(filePath);
                    if (!pageSequence.isEmpty()) break;
                    else System.out.println("错误：文件读取失败或序列为空！");
                } else {
                    System.out.println("错误：请选择1或2！");
                }
            } catch (InputMismatchException e) {
                System.out.println("错误：请输入整数！");
                scanner.next();
            }
        }
        return pageSequence;
    }

    /**
     * 解析页面序列字符串（逗号分隔）
     */
    private static List<Integer> parsePageSequence(String input) {
        List<Integer> sequence = new ArrayList<>();
        if (input.isEmpty()) return sequence;
        String[] parts = input.split(",");
        for (String part : parts) {
            try {
                int page = Integer.parseInt(part.trim());
                if (page >= 0) {
                    sequence.add(page);
                } else {
                    System.out.println("警告：忽略负页面号 " + page);
                }
            } catch (NumberFormatException e) {
                System.out.println("警告：忽略非法字符 " + part);
            }
        }
        return sequence;
    }

    /**
     * 从文件读取页面序列
     */
    private static List<Integer> readPageSequenceFromFile(String filePath) {
        List<Integer> sequence = new ArrayList<>();
        try (BufferedReader br = new BufferedReader(new FileReader(filePath))) {
            String line = br.readLine(); // 读取第一行作为页面序列
            if (line != null) {
                sequence = parsePageSequence(line.trim());
            }
        } catch (IOException e) {
            System.out.println("错误：文件读取失败！" + e.getMessage());
        }
        return sequence;
    }

    /**
     * LRU核心算法模拟
     * @param blockNum 物理块数量
     * @param pageSequence 页面访问序列
     * @return 包含访问过程和统计结果的Map
     */
    private static Map<String, Object> simulateLRU(int blockNum, List<Integer> pageSequence) {
        List<AccessResult> accessResults = new ArrayList<>();
        List<Integer> physicalBlocks = new ArrayList<>(); // 模拟物理块，顺序：左=最近最少使用，右=最近使用
        int hitCount = 0;
        int totalAccess = pageSequence.size();

        for (int i = 0; i < totalAccess; i++) {
            int currentPage = pageSequence.get(i);
            int seqNum = i + 1;
            String resultDesc;

            if (physicalBlocks.contains(currentPage)) {
                // 页面命中：移到末尾（标记为最近使用）
                physicalBlocks.remove(Integer.valueOf(currentPage));
                physicalBlocks.add(currentPage);
                resultDesc = "命中";
                hitCount++;
            } else {
                // 页面未命中：需要置换（若物理块满）
                resultDesc = "未命中";
                if (physicalBlocks.size() < blockNum) {
                    // 物理块未满，直接加入末尾
                    physicalBlocks.add(currentPage);
                } else {
                    // 物理块已满，淘汰最左侧（最近最少使用）页面
                    int eliminatedPage = physicalBlocks.remove(0);
                    physicalBlocks.add(currentPage);
                    resultDesc += "（淘汰" + eliminatedPage + "）";
                }
            }

            // 记录当前访问结果（复制物理块状态，避免后续修改影响）
            List<Integer> currentBlocks = new ArrayList<>(physicalBlocks);
            accessResults.add(new AccessResult(seqNum, currentPage, currentBlocks, resultDesc));
        }

        // 计算统计信息
        int missCount = totalAccess - hitCount;
        double hitRate = (double) hitCount / totalAccess * 100;
        Statistic statistic = new Statistic(totalAccess, hitCount, missCount, hitRate);

        Map<String, Object> resultMap = new HashMap<>();
        resultMap.put("accessResults", accessResults);
        resultMap.put("statistic", statistic);
        return resultMap;
    }

    /**
     * 打印逐次访问结果表格
     */
    private static void printAccessTable(List<AccessResult> accessResults) {
        System.out.println("\n===== 页面访问过程 =====");
        // 表头
        System.out.printf("%-8s %-8s %-15s %-10s%n",
                "访问序号", "访问页面", "物理块状态", "访问结果");
        System.out.println("----------------------------------------");
        // 逐行输出
        for (AccessResult ar : accessResults) {
            // 物理块状态格式化：[a,b,c]
            String blockStr = ar.blocks.stream()
                    .map(String::valueOf)
                    .collect(Collectors.joining(","));
            System.out.printf("%-8d %-8d [%-13s] %-10s%n",
                    ar.seqNum, ar.page, blockStr, ar.result);
        }
    }

    /**
     * 打印统计结果
     */
    private static void printStatistic(Statistic statistic) {
        System.out.println("\n===== 实验统计结果 =====");
        DecimalFormat df = new DecimalFormat("#.00"); // 保留2位小数
        System.out.println("总访问次数：" + statistic.totalAccess);
        System.out.println("命中次数：" + statistic.hitCount);
        System.out.println("未命中次数：" + statistic.missCount);
        System.out.println("页面命中率：" + df.format(statistic.hitRate) + "%");
    }
}
